package mid.class1;


import common.ArrayUtils;

/**
 * 求最大回文子串
 * 1.将字符串用`#`处理
 */
public class Code04_Manacher {

    public static void main(String[] args) {
        String str = "32122131221";
//        char[] res = getManacherString("abacabacabb");
        int manacher = manacher(str);
        ArrayUtils.printArr(manacher);
    }

    public static char[] getManacherString(String str) {
        char[] arr = str.toCharArray();
        char[] ans = new char[str.length() * 2 + 1];
        for (int i = 0, index = 0; i < ans.length; i++) {
            ans[i] = (i & 1) == 0 ? '#' : arr[index++];
        }
        return ans;
    }

    /**
     * 回文子串的三种情况
     * 1.子串完全在L..R的范围内
     * 2.子串i的镜像位置，回文串长度一段超过了L..R的范围
     * 3.子串i的镜像正好L..R之间压线
     */
    public static int manacher(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // 1223221 -> #1#2#2#3#2#2#1
        // s-> 处理串 str
        char[] str = getManacherString(s);
        System.out.println(new String(str));
        // 左回文半径
        int[] pArr = new int[str.length];
        int C = -1; // 中心
        int R = -1; // 回文右边界再往右一个位置，最右有效区是 R-1
        int max = Integer.MIN_VALUE;
        for (int i = 0; i != str.length; i++) { // 向两边扩
            // 如果当前i在回文右边界以内，则用对称位置的回文半径的最小值
            // 否则初始化回文半径为1               // 求出不用验证的区域
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                if (str[i + pArr[i]] == str[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
                if (i + pArr[i] > R) {
                    R = i + pArr[i];
                    C = i;
                }
                max = Math.max(max, pArr[i]);
            }
            ArrayUtils.printArr(pArr);
        }
        return max - 1;
    }

    //            if(i在R外部){
//                // 从 i 开始往两边暴力扩：R变大
//                R++;
//            }else{
//                if(i`的回文区域彻底在L..R内){
//                    lArr[]
//                }else if(i`回文区域有一部分在L..R外){
//
//                }else{ // i`回文区域和L..R的左边界压线
//                    //从R之外的字符开始，往外扩，然后确定pArr[i]的答案；
//                    // 第一步失败了R不变，否则R变大
//
//                }
//            }
}
